// 二叉树遍历
function traverse(node, callback) {
  if (node === null) {
    return;
  }

  // 前序
  callback(node);

  if (node.left) {
    traverse(node.left, callback);
  }

  // 中序
  // callback(node);

  if (node.right) {
    traverse(node.right, callback);
  }

  // 后序
  // callback(node);
}

// 层级遍历
// 迭代写法
function bfs(root) {
  if (root === null) {
    return;
  }
  let queue = [];
  queue.push(root);
  while (queue.length > 0) {
    let node = queue.shift();

    // console.log(node.value);
    for (const item of node.children) {
      queue.push(item);
    }

    console.log(node.value);
  }
}

function bfs2(nodes) {
  if (nodes.length === 0) {
    return;
  }

  let queue = [];

  for (const node of nodes) {
    console.log(node.value);
    if (node.children) {
      queue.push(...node.children);
    }
  }

  return bfs2(queue);
}

// 对比一下两种的区别

// 深度优先
function dfs(node, callback) {
  if (node === null) {
    return;
  }

  // 进入节点
  callback(node);

  // 遍历子节点
  for (let child of node.children) {
    dfs(child, callback);
  }

  // 离开节点
  callback(node, callback);
}

// 回溯算法模版
function backtrack(node, choice) {
  if (node === null) {
    return;
  }

  for (let child of node.children) {
    // 同时这里还能进行 剪裁优化
    // 作选择
    choice.push(child);
    // 遍历子节点
    backtrack(child, choice);
    // 撤销选择
    choice.pop();
  }
}
